/*
 * @lc app=leetcode.cn id=324 lang=java
 *
 * [324] 摆动排序 II
 */

// @lc code=start
class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int k = (n+1) / 2 - 1;  // 找到中位数的位置
        finkK(nums, 0, n-1, k); // 找到这个数分割数组
        threeWayPartition(nums, 0, n-1, k);  // 将两部分=x的值移动到两侧

        int[] tmp = nums.clone();

        for(int i = 0, j = n-1, t = k; i < n; i += 2, j--,t--) {
            nums[i] = tmp[t];
            if(i + 1 < n) {
                nums[i+1] = tmp[j];
            }
        }
    }

    private void finkK(int[] nums, int s, int e, int k) {
        int i = s, j = i;
        int t = nums[s];
        while(j <= e) {
            if(nums[j] < t) {
                swap(nums, ++i, j++);
            } else {
                j++;
            }
        }

        swap(nums, s, i);
        if(i < k) {
            finkK(nums, i+1, e, k);
        } else if(i > k) {
            finkK(nums, s, i-1, k);
        }
    } 

    private void threeWayPartition(int[] nums, int s, int e, int k) {
        int i = s, j = e, a = s;
        int t = nums[k];
        while (a < j) {
            if (nums[a] < t) {
                swap(nums, a++, i++);
            } else if (nums[a] > t) {
                swap(nums, a, j--);
            } else {
                a++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
// @lc code=end

